/**
 * Transform a map of wiki articles to terms to a map from terms to Netflix 
 * movie ids. This is similar to reversing an adjacency list
 * (u1/ReverseLinks.java) but we only keep track of movies, and we look up the
 * Netflix movie ids.
 *
 * Usage:
 * ... movies_with_ids <adj
 *
 * movies_with_ids has format:
 * netflix_movie_id wiki_article_ordinal
 * (like big.new.movies.with_ids)
 * adj has format:
 * wiki_article_ordinal num_terms term term ...
 * wiki_article_ordinal num_terms term term ...
 * ...
 * where each term is a non-negative integer.
 *
 * Output (on standard out):
 * term num_pages num_movies movie_id movie_id...
 * term num_pages num_movies movie_id movie_id...
 * ...
 * where num_pages is the number of wikipedia articles corresponding to
 * movies that the term appears on, and num_movies is the number or movies
 * for which the corresponding wikipedia articles contain the term. Note that
 * 1 <= num_pages <= num_movies for all terms, since only terms that occur on
 * some movie page are returned, and several movies may map to a single page. 
 *
 */ 
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include "u1.h"

using namespace std;

typedef multimap<int, int> ids_t;
typedef multimap<int, int> terms_t;

void write_term(int term, int page_count, const set<int> &movie_ids) {
  assert(0 < page_count && page_count <= (int)movie_ids.size());
  cout<<term<<' '<<page_count<<' '<<movie_ids.size()<<' ';
  copy(movie_ids.begin(), movie_ids.end(),
      ostream_iterator<int>(cout, " "));
  cout<<'\n';
}

int main(int argc, char **argv)
{
  if (argc != 2) {
    TRACE<<"see comments for usage"<<endl;
    exit(EXIT_FAILURE);
  }
  string ids_file = argv[1];

  TRACE<<"Reading movie - article ids from "<<ids_file<<endl;
  ids_t ids;
  ifstream ids_in(ids_file.c_str());
  int movie_id, article_num;
  while (ids_in>>movie_id>>article_num) {
    assert(1 <= movie_id && movie_id <= 17770);
    ids.insert(make_pair(article_num, movie_id));
  }
  ids_in.close();
  TRACE<<"Read "<<ids.size()<<" pairs."<<endl;

  TRACE<<"Reading adj from stdin and building terms list."<<endl;
  terms_t term_movies;
  map<int, int> term_page_counts;
  int num_terms;
  while(cin>>article_num>>num_terms) {
    // Only process movie articles.
    if (ids.find(article_num) == ids.end()) {
      // Must still run through the terms to get them off the input stream.
      for (int i = 0; i < num_terms; ++i) {
        int term;
        if (!(cin>>term)) {
          TRACE<<"Expected "<<num_terms<<" terms for article "<<article_num
            <<" but got "<<i<<endl;
          exit(EXIT_FAILURE);
        }
      }
    } else {
      for (int i = 0; i < num_terms; ++i) {
        int term;
        if (!(cin>>term)) {
          TRACE<<"Expected "<<num_terms<<" terms for article "<<article_num
            <<" but got "<<i<<endl;
          exit(EXIT_FAILURE);
        }

        // Record that the current page contains this term.
        map<int,int>::iterator tpc_it = term_page_counts.find(term);
        if (tpc_it == term_page_counts.end()) {
          term_page_counts.insert(make_pair(term, 1));
        } else {
          ++(tpc_it->second);
        }
        
        // Several movies can be mapped to one article.
        pair<ids_t::iterator,ids_t::iterator> range =
          ids.equal_range(article_num);
        for (ids_t::iterator it = range.first; it != range.second; ++it) {
          assert(1 <= it->second && it->second <= 17770);
          term_movies.insert(make_pair(term, it->second));
        }
      }
    }
  }

  TRACE<<"Writing "<<term_movies.size()<<" terms to stdout."<<endl;
  int term = -1;
  set<int> movie_ids;
  for (terms_t::const_iterator it = term_movies.begin();
      it != term_movies.end(); ++it)
  {
    if (it->first != term) {
      if (term != -1)
        write_term(term, term_page_counts[term], movie_ids);
      term = it->first;
      movie_ids.clear();
    }
    movie_ids.insert(it->second);
  }
  if (term != -1)
    write_term(term, term_page_counts[term], movie_ids);
  TRACE<<"Done."<<endl;
}
/*
* Copyright (c) 2009 John Lees-Miller
* 
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/

